package com.shuo.dsa.leetcode;

import com.shuo.dsa.model.ListNode;

/**
 * 寻找环形链表的环形起始点
 *      思路: 快慢指针寻找出交点z, 然后让head和z同时单步前进, 相交点即为起始点
 */
public class FineListCircleNode {
    public ListNode detectCycle(ListNode head) {
        if (head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode h = head;
                ListNode z = slow;
                while (h != z) {
                    h = h.next;
                    z = z.next;
                }
                return h;
            }
        }
        return null;
    }
}
